\chapter{Optimizations on low-level representation}

\section{Register allocation}

\subsection{Estimated distance of use}

We define a metric associated with every control arc in the flow
graph.  The metric is called \emph{Estimated Distance to Use} or EDU
for short.  It assigns a number to each lexical variable, reflecting
how far in the future that lexical variable is needed.  The EDU metric
is a generalization of \emph{liveness} information, where and EDU
value of $\infty$ means that the variable is dead.

For some instruction $I$ with an incoming control arc $A$ and a
variable $V$ that is read or written by $I$, the EDU value of $V$ in
$A$, is defined to be $1$, i.e. $E(V)_A = 1$.

For some instruction $I$ with an incoming control arc $A$ and a single
outgoing control arc $B$ such that $V$ is neither read nor written by
$I$, if $E(V)_B \not = \infty$ the EDU value of $V$ in $A$, $E(V)_A =
1 + E(V)_b$ where $E(V)_b$ is the EDU value of $V$ in $B$.  If
$E(V)_b = \infty$, then $E(V)_A = \infty$ as well.

For some instruction $I$ with an incoming control arc $A$ and two
outgoing control arcs $B_1$ $B_2$ such that $V$ is neither read nor
written by $I$, the EDU value of $V$ in $A$, we compute $E(V)_A$ as
follows.  Let $p_1$ be the estimated probability that the control arc
$B_1$ will be used, and $p_2$ be the estimated probability that the
control arc $B_2$ will be used.  If $E(V)_{B_1} \not = \infty$ and
$E(V)_{B_2} \not = \infty$ then $E(V)_A = 1 + {{E(V_{B_1})E(V_{B_2})}
  \over {p_2 E(V_{B_1}) + p_1 E(V_{B_2})}}$.  If $E(V)_{B_1} = \infty$
and $E(V)_{B_2} \not = \infty$ then $E(V)_A = 1 + {{E(V_{B_2})} /
  p_2}$.  If $E(V)_{B_1} \not = \infty$ and $E(V)_{B_2} = \infty$ then
$E(V)_A = 1 + {{E(V_{B_1})} / p_1}$.  If $E(V)_{B_1} = \infty$ and
$E(V)_{B_2} = \infty$ then $E(V)_A = \infty$.

We use an iterative procedure to compute the EDU values, propagating
from \texttt{return} instructions and following control arcs in
reverse.  This procedure does not automatically halt, because of loops
in the control graph.  But EDU values are only approximate, so we stop
propagating modifications when new values differ little from old
ones.

\subsection{Variable map}

Next, we use the EDU values to compute a \emph{variable map}
associated with each control arc in the flow graph.  The map contains
two items:

\begin{enumerate}
\item A vector of \emph{stack location} that are either currently in
  use, or that that have been used in the past.  The size of the
  vector reflects the required number of locations required in the
  stack frame.  An element of the vector is either a lexical variable,
  or \texttt{nil} if the corresponding stack location contains no
  valid datum.
\item A vector with the same size as the number of registers
  available.  An element of the vector is either a lexical variable,
  or \texttt{nil} if the corresponding register contains no valid
  datum.
\end{enumerate}

For a particular control arc, every live variable is contained either
in the first vector, in the second vector, or in both vectors.  For
the time being, we imagine that a lexical variable can be present in
at most one register and in at most one stack location.

Initially, suppose we have a load/store architecture, so that the flow
graph contains instructions that require all their operands in
registers.  We assume that the flow graph does not contain any
\texttt{load} or \texttt{store} instructions.

We compute variables maps from the start of the flow graph.  The
initial map contains the situation upon function entry, as dictated by
the function-call protocol.  For all other control arcs, initialize
all maps to \emph{unknown}.

Let $I$ be an instruction with a single incoming control arc $A$.  For
each Variable $V$ such that $E(V)_A = 1$, we must make sure that $V$
is in a register before $I$ is executed.  If $V$ is already in a
register, no action needs to be taken.  If $V$ is in a stack location,
and there is at least one register containing no valid datum, then
emit a \texttt{load} instruction and update the map.  If $V$ is in a
stack location, but every register contains some valid datum, then we
must choose a \emph{victim}, i.e. a lexical variable $W$ that is
currently in a register.  The decision depends on whether $W$ is also
present in a stack location, and on $E(W)_a$.  It is preferable to
choose a $W$ with a large value of $E(W)_a$ and it is preferable to
choose one that is also present in some stack location.  If a $W$ is
chosen that is also present in a stack location, then a \texttt{load}
instruction is emitted to load $V$ to the register previously occupied
by $W$ and the map is updated accordingly.  If $W$ is not present in a
stack location, then a \emph{store} instruction must first be emitted
to store the variable into a stack location.  If all stack locations
are occupied, then the vector of stack locations will have its size
increased.

Now, let $I$ be an instruction with several incoming control arcs.%
\footnote{To be continued.}
